package com.zzz.offer.ischildtree;

public class IsChildTree2 {
    // 看过代码后这个栈完全不需要
    //Stack<TreeNode> stackMater = new Stack<>();
    //Stack<TreeNode> stackChild = new Stack<>();

    // 直接 通过遍历左树右树 而不需要设置一个 list 装所有树的节点
    //List<TreeNode> tree = new ArrayList<>();

    public boolean HasSubtree(TreeNode root1, TreeNode root2) {

        if (root1 == null || root2 == null) {
            return false;
        }

        //这一块代码不需要了
        //listNode(root1);
        //for (TreeNode treeNode : tree) {
        //    if (checkIsChildTree(treeNode, root2)) {
        //        return true;
        //    }
        //}

        // 直接 递归调用 左树节点  和  右树节点。。。牛逼
        return checkIsChildTree(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);

        //return false;

    }

    // 无需遍历树
//    public void listNode(TreeNode node) {
//        if (node == null) {
//            return;
//        }
//        tree.add(node);
//
//        listNode(node.left);
//        listNode(node.right);
//    }

    public boolean checkIsChildTree(TreeNode treeA, TreeNode treeB) {

        // 如果treeB节点为空 那直接返回true  treeB的孩子节点为空不需要进行比较
        if (treeB == null) {
            return true;
        }

        // 比较规则
        // treeB 不为空，那么就必须要求 treeA不为空且必须 值相同 相同返回true，不同返回false
        // 若treeB节点为空那么 就相当于成功，返回true

        // 1.比较当前结点  如果返回false 直接返回 如果返回true，接着比较左孩子节点
        if (treeA == null || treeA.val != treeB.val) {
            return false;
        }

        // 如果是根节点，那必须先清空上一次匹配生成的stack
        //if (isRoot) {
        //    stackMater.clear();
        //    stackChild.clear();
        //}

        // 该节点匹配成功，就将节点加入 stack 中
        //stackMater.push(treeA);
        //stackChild.push(treeB);


        // 2.比较左孩子   如果返回false 直接返回 如果返回true，接着比较右孩子节点
        if (!checkIsChildTree(treeA.left, treeB.left)) {
            return false;
        }

        // 3.比较右孩子   如果返回false 直接返回 如果返回 true 就相当于本节点包括子树都匹配成功， 返回true
        return checkIsChildTree(treeA.right, treeB.right);

        //stackMater.pop();
        //stackChild.pop();

        // 4.判断当前是否是根节点层，如果是判断Stack 是否 是空，
        // 如果是空表示 匹配子树成功，否则 当前节点未匹配到，
        //  ---------------------------------------------
        // 想了想，若是出现匹配异常就直接返回false了，不需要判断stack是否为空
    }
}
